package com.cong.sort.quick;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author cong
 *         <p>
 *         created on 2021/3/19 下午3:23
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = { 7, 3, 2, 10, 8, 1, 9, 5, 4, 6 };
        print(arr);

        sort(arr, 0, arr.length - 1);

        System.out.println();
        print(arr);

    }

    public static void sort(int[] arr, int left, int right) {
        // 数组中只有一个元素
        if (left >= right)
            return;
        int mid = partition(arr, left, right);
        // 轴左边排序
        sort(arr, left, mid - 1);
        // 轴右边排序
        sort(arr, mid + 1, right);

    }

    /**
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     * @return 轴的位置
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        System.out.println(pivot);
        int l = left;
        int r = right - 1;
        // 当左边小于右边，一直循环
        while (l <= r) {
            // 当l小于pivot,一直往右找i
            while (l <= r && arr[l] <= pivot)
                l++;
            while (l <= r && arr[r] > pivot)
                r--;
            if (l < r)
                swap(arr, l, r);
        }
        // if (arr[l]>arr[right])
        swap(arr, l, right);
        System.out.println(Arrays.toString(arr));
        return l;
    }

    /**
     * 交换
     * 
     * @param arr
     * @param source
     * @param target
     */
    static void swap(int[] arr, int source, int target) {
        int temp = arr[target];
        arr[target] = arr[source];
        arr[source] = temp;
    }

    static void print(int[] arr) {
       System.out.println(Arrays.toString(arr));
    }
}
